This invention relates to apparatus and methods for storing data on magnetic media and in particular to such apparatus and methods which implement at least two levels of error correction.
There is a continually increasing demand for magnetic data storage devices capable of storing large volumes of digital data, such as computer data on magnetic tape by means of the DDS (Digital Data Storage) Format. In a DDS read/write mechanism using the above format, data are recorded in helical scan fashion on an elongate recording media, comprising a tape coated with a magnetic medium, by a rotating drum carrying one or more electromagnetic heads. The tape is moved by a motor-driven capstan along a path extending between two spools or reels and wrapped partially around the drum. The plane of rotation of the heads of the drum is disposed at an angle to the plane of movement of the tape, so that each head traverses the tape along successive tracks extending across the width of the tape at an angle to its centre line. The mechanism includes appropriate circuitry for encoding data into signals suitable for recording onto tape, including error-detection and correction codes, and for conditioning those signals into a form optimally matched to the characteristics of the recording media. For data retrieval, additional circuitry is provided for detecting magnetic field variations stored on the tape, deriving corresponding signals, conditioning those signals into a form for subsequent processing, decoding the encoded data and detecting and correcting errors.
A recent development has been the DDS3 format (defined in ECMA Standard ECMA-236 dated June 1996 xe2x80x9c3,81 mm Wide Magnetic Tape Cartridge for Information Interchangexe2x80x94Helical Scan Recordingxe2x80x94DDS-3 Format using 125 m Length Tapesxe2x80x9d, the entire contents of which are incorporated herein by reference). In DDS3, error checking and detection is achieved by using a multilevel interleaved Reed-Solomon code providing at least two levels (C1, C2) and optionally a third level (C3) of error correction coding (ECC). In addition, to provide a final data check on reading, track checksums are generated corresponding to each track of data to be written on tape, and stored in the fragment headers, several of which are incorporated in each track. Thus on reading, the track checksum algorithm is applied to the data bytes retrieved from the tape and if this tracksum does not agree with that calculated and stored when the tape was recorded, the track is rejected.
It is desirable that the track checksum operates to reject as large a proportion as possible of failed tracks (that is ones containing either uncorrectable or miscorrected codewordsxe2x80x94as to be described below). Although the existing track checksum operates reasonably well, the Applicant has discovered that there is an unexpected yet significant flaw in this system, such that the track checksum does not identify a large proportion of miscorrections. The Applicant""s analysis has revealed that, in a miscorrected codeword in which the xe2x80x9ccorrectionsxe2x80x9d occur in the data bytes only of the codeword, the track checksum will not reveal this failure. This phenomenon arises because the codewords are constructed to have the inherent property that the result of XORing all the bytes together (both data and parity) is zero. Also in DDS3 the track checksums are calculated by XORing the data bytes of the relevant track.
Given that the bytes of a good (or miscorrected) codeword XOR to zero, if the parity bytes of a particular good or miscorrected codeword XOR to, say, a binary value A, the data bytes must also XOR to the same value A (so that the data bytes and parity bytes together XOR to zero). In a miscorrection of this particular codeword, in which the xe2x80x9ccorrectionsxe2x80x9d are contained in the data bytes only, the parity bytes will XOR to A as previously because they are unchanged. Even though the data bytes have changed, the data bytes will still XOR to A to fulfil the requirement that the miscorrection XORs to zero. However, the data bytes all contribute to the same checksum (also the result of an XOR operation) the track checksum will remain unchanged, and so, for this type of miscorrection, due to the correlation between the inherent XOR property of the codeword and the operation used to calculate the checksum, the track checksum will not reveal a miscorrected codeword in which all the xe2x80x9ccorrectionsxe2x80x9d appear in the data bytes.
The Applicants have determined that modifying the track checksum algorithm so that is does not correlate with the XOR operation provides a reliable method for detecting miscorrections in the previous codeword. The ability to detect miscorrections reliably also has important beneficial consequences when third level C3 correction is implemented.
In the past the Applicants have attempted to use the track checksum to identify C2 codeword failures and mark them accordingly. Because of the interleaved and multi-level structure of the error correction coding, if a codeword fails at the C1 or C2 levels (in a three level system), knowing the position of that codeword in the array identifies in the codewords of the next level the locations of a number of bytes which are suspect. The structure of the error correction coding means that the bytes in a particular codeword map to positions in the subsequent codewords according to a known mapping. Thus a failed codeword at the C2 stage can be used to flag particular bytes in the C3 codeword to the C3 correction algorithm so that these are treated as xe2x80x9cerasuresxe2x80x9d rather than errors.
Thus when a complete C2 codeword is marked as a failure, the corresponding data byte locations making up the codeword may be determined so that o the next, C3, level the location of the errors is known. A Reed-Solomon code having N parity bytes is capable of correcting xe2x80x98exe2x80x99 errors and xe2x80x98vxe2x80x99 erasures, where 2e+vxe2x89xa6N, and an erasure is a bad byte in a known location. A typical C3 correction codeword has just two parity bytes (i.e. N=2) and so the C3 correction algorithm can either correct a single error (e=1) or two erasures (v=2). Where two corrections are made this is referred to as double error correction. Thus the ability reliably to mark miscorrected C2 codewords as erasures would mean that the C3 algorithm could perform double error correction. Until now, the absence of a reliable method of detecting miscorrections has meant that it has not been realistic to attempt double error correction at the C3 stage.
Accordingly, the Applicants have provided a method and apparatus in which the track checksum provides considerably more reliable checking of miscorrections in one aspect this invention provides apparatus for storing a stream of data records on magnetic media, said apparatus including:
group formatting means for grouping said data records into groups of data bytes;
sub-group processing means for dividing each of said groups into subgroups, wherein each subgroup comprises data bytes corresponding to one or more data tracks;
track checksum calculating means for calculating one or more checksums for the or each data track,
means for transforming each subgroup into at least one respective array, each corresponding to a data track,
first error correction coding encoding means for encoding columns of the or each array to provide first (C1) ECC codewords comprising data bytes and parity bytes;
second error correction coding encoding means for encoding rows of the or each array to provide second (C2) ECC codewords comprising data bytes and parity bytes;
wherein said track checksum calculating means calculates a respective track checksum for the or each track such that, on decoding of said ECC codewords, a miscorrected codeword in which the miscorrections are in the data bytes only has no more than a substantially random probability of providing the same contribution to the corresponding track checksum as the corresponding original codeword.
It is emphasized that the terms xe2x80x9cfirstxe2x80x9d and xe2x80x9csecondxe2x80x9d are not intended to require that the first error correction coding means operates before the second error correction coding means.
In this way, selecting a track checksum algorithm which has no correlation with the codeword generation rules means that the track checksum is more reliable for detecting miscorrections than the previous correction algorithm. In turn this makes it possible to use the track checksums to mark miscorrected codewords with considerably enhanced correction rates.
Preferably said first and second error correction coding encoding means apply respective Reed-Solomon coding algorithms.
There are many algorithms which may be used to generate the track checksum; in one particular example where Reed-Solomon codewords having a root at xcex10 are used, the track checksum may be calculated on the basis of the arithmetic addition of the data bytes in the relevant track.
The codewords and the checksums may be processed in a variety of ways prior to writing to tape, but it is preferred for the apparatus to include means for transforming said encoded arrays to provide for each track a plurality of data fragments for being written on said magnetic media, and fragment header means for providing each of said data fragments with a fragment header, wherein at least some of said fragment headers include data bytes identifying the corresponding track checksum for the current track.
The provision of a more reliable track checksum scheme for detecting miscorrections facilitates double error correction at a third level. Accordingly, the apparatus preferably includes third error correction encoding means for computing codewords from respective corresponding byte positions across each of the tracks making up a group.
The invention also extends to a method for storing a stream of data records on magnetic media, which comprises:
grouping said data records into groups of data bytes, dividing each of said groups into subgroups of data bytes, each subgroup corresponding to one or more data tracks;
calculating and storing one or more track checksums for the or each data track;
transforming each subgroup into at least one respective array each corresponding to a data track; encoding columns of said the or each array to form first error correction coding codewords comprising data bytes and parity bytes;
encoding rows of said the or each array to form second error correction coding codewords comprising data bytes and parity bytes;
wherein said track checksum calculating means calculates a respective track checksum for the or each track such that, on decoding of said correction coding codewords, a miscorrected codeword in which the miscorrections are in the data bytes has no more than a substantially random probability of providing the same contribution to the corresponding track checksum as the corresponding original codeword.
The invention also extends to a method for reading data stored in accordance with the above method, which comprises retrieving data from tape, extracting therefrom said track checksums, decoding the codewords to obtain data bytes for each track, computing a track checksum for the decoded data bytes, and flagging a failure if said checksums do not agree.
Preferably said data includes three levels of error correction, and said track checksum is used after the second level of error correction to flag any second codeword failures thereby to identify and mark as erasures to the third level correction algorithm any data bytes in the third level codewords which correspond to a second level codeword failure.
Whilst the invention has been described above it extends to any inventive combination of the features set out above or in the following description.